package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/additive-number/">306.累加数</a>
 */
public class Solution306 extends BaseSolution {

    public boolean isAdditiveNumber(String num) {
        int len = num.length();
        int maxLen = (len + 1) * 2 / 3;
        for (int i = 1; i <= maxLen; i++) {
            for (int j = 1; j <= maxLen - i; j++) {
                if (i + j >= len) {
                    break;
                }
                String n1 = num.substring(0, i);
                String n2 = num.substring(i, i + j);
                boolean rst = checkToEnd(num, i + j, n1, n2);
                if (rst) {
                    return true;
                }
                if (num.charAt(i) == '0') {
                    break;
                }
            }
            if (num.charAt(0) == '0') {
                break;
            }
        }
        return false;
    }

    private boolean checkToEnd(String num, int p, String n1, String n2) {
        String sum = add(n1, n2);
        int nL = num.length();
        if (p >= nL) {
            return true;
        }
        return num.startsWith(sum, p) && checkToEnd(num, p + sum.length(), n2, sum);
    }

    private String add(String n1, String n2) {
        int p1 = n1.length() - 1, p2 = n2.length() - 1, floor = 0;
        StringBuilder stringBuilder = new StringBuilder();
        while (p1 >= 0 && p2 >= 0) {
            char c1 = n1.charAt(p1--);
            char c2 = n2.charAt(p2--);
            int t = c1 + c2 + floor - 2 * '0';
            stringBuilder.append(t % 10);
            floor = t / 10;
        }
        while (p1 >= 0) {
            int t = n1.charAt(p1--) + floor - '0';
            stringBuilder.append(t % 10);
            floor = t / 10;
        }
        while (p2 >= 0) {
            int t = n2.charAt(p2--) + floor - '0';
            stringBuilder.append(t % 10);
            floor = t / 10;
        }
        if (floor != 0) {
            stringBuilder.append(floor);
        }
        return stringBuilder.reverse().toString();
    }

    public static void main(String[] args) {
        Solution306 solution = new Solution306();
        System.out.println(solution.isAdditiveNumber("0999999999999999999999999999999999999999999"));
        System.out.println(solution.isAdditiveNumber("199100"));
        System.out.println(solution.isAdditiveNumber("000"));
        System.out.println(solution.isAdditiveNumber("0235813"));
        System.out.println(solution.isAdditiveNumber("101"));
        System.out.println(solution.isAdditiveNumber("112358"));
        System.out.println(solution.isAdditiveNumber("121325"));
        System.out.println(solution.isAdditiveNumber("12132"));
        System.out.println(solution.isAdditiveNumber("235881"));
    }
}